package leetcode.solution;

/**
 * @author : zx
 * @version V1.0
 */
public class MaxProfit {

    public static int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n == 0 || k < 2){
            return 0;
        }
        if (k >= n/2){
            return getProfit_kn(prices);
        }else {
            // 天数、第几次交易、是否持有股票(0不持股、1持股） 的现金
            int[][][] dp = new int[n][k][2];
            for(int i = 0; i < n; i++){
                for (int j = 0; j < k; j++){
                    dp[i][j][1] = Integer.MIN_VALUE;
                }
            }
            for (int i = 0; i < n; i++){
                for (int j = 0; j < k; j++){
                    if (i == 0){
                        dp[i][j][0] = 0;
                        dp[i][j][1] = -prices[0];
                    }else {
                        if (j == 0){
                            dp[i][j][1] = Math.max(dp[i-1][j][1], - prices[i]);
                        }else {
                            // 状态转移 继续持有 或者 买入 （如当前交易日买入股票成本大于前一交易日买入股票怎买入）
                            dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
                        }
                        // 状态转移 不买入 或 卖出
                        dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
                    }
                }
            }
            return dp[n-1][k-1][0];
        }
    }

    /**
     * 因为dp[i]只和dp[i-1]有关，因此可以去掉一维
     * @param k
     * @param prices
     * @return
     */
    public static int maxProfit_mini(int k, int[] prices) {
        int n = prices.length;
        if (n == 0 || k < 1){
            return 0;
        }
        if (k >= n/2){
            return getProfit_kn(prices);
        }else {
            // 第几次交易、是否持有股票(0不持股、1持股）
            int[][] dp = new int[k][2];
            for(int i = 0; i < n; i++){
                for (int j = 0; j < k; j++){
                    dp[j][1] = Integer.MIN_VALUE;
                }
            }
            for (int i = 0; i < n; i++){
                for (int j = 0; j < k; j++){
                    if (i == 0){
                        dp[j][0] = 0;
                        dp[j][1] = -prices[0];
                    }else {
                        if (j == 0){
                            dp[j][1] = Math.max(dp[j][1], - prices[i]);
                        }else {
                            // 状态转移 不操作 或者 买入
                            dp[j][1] = Math.max(dp[j][1], dp[j-1][0] - prices[i]);
                        }
                        // 状态转移 不操作 或 卖出
                        dp[j][0] = Math.max(dp[j][0], dp[j][1] + prices[i]);
                    }
                }
            }
            return dp[k-1][0];
        }
    }

    /**
     * 必须隔一天卖出
     * @param k
     * @param prices
     * @return
     */
    public static int maxProfit_cantsell(int k, int[] prices) {
        int n = prices.length;
        if (n == 0 || k < 1){
            return 0;
        }
        if (k >= n/2){
            return getProfit_kn(prices);
        }else {
            // 第几次交易、是否持有股票(0不持股、1持股）
            int[][] dp = new int[k][2];
            for(int i = 0; i < n; i++){
                for (int j = 0; j < k; j++){
                    dp[j][1] = Integer.MIN_VALUE;
                }
            }
            int pre = 0;
            for (int i = 0; i < n; i++){
                for (int j = 0; j < k; j++){
                    int tmp = dp[j][1];

                    if (i == 0){
                        dp[j][0] = 0;
                        dp[j][1] = -prices[0];
                    }else {
                        if (j == 0){
                            dp[j][1] = Math.max(dp[j][1],  - prices[i]);
                        }else {
                            // 状态转移 继续持有 或者 买入
                            dp[j][1] = Math.max(dp[j][1], dp[j-1][0] - prices[i]);
                        }
                        // 状态转移 不买入 或 卖出 (和前天的持仓比较）
                        dp[j][0] = Math.max(dp[j][0], pre + prices[i]);
                    }
                    pre = tmp;
                }
            }
            return dp[k-1][0];
        }
    }

    private static int getProfit_kn(int[] prices){
        int n = prices.length;
        int profit = 0;
        for (int i = 1; i < n; i++){
            if (prices[i] > prices[i-1]){
                profit += prices[i] - prices[i-1];
            }
        }
        return profit;
    }


    private static int getProfit_k1(int[] prices){
        int n = prices.length;
        int stock = prices[0];
        int profit = 0;
        for (int i = 1; i < n; i++){
            stock = Math.max(stock, prices[i]);
            profit = Math.max(profit, prices[i] - stock);
        }
        return profit;
    }

    public static void main(String[] args){
        int[] a = {5,2,4,5,8,1,8};
        System.out.println(maxProfit_mini(1, a));
        System.out.println(maxProfit_cantsell(1, a));
    }
}
